哈希表

排序

手写系列

146. LRU 缓存

企鹅电竞手写

题目

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

单链表解法

1. 用单链表来存储节点；引入哑元节点
2. put(key, value) 方法
   1. 首先根据 key 查找链表是否存在该元素，如果存在，先删除，然后返回该元素，将新的 value 替换旧的 val，再插入到头节点去
   2. 如果链表不存在该节点，那么看 size 是否超过了 capacity
   3. size 未超过 capacity，插入一个新的节点到头节点，size 加 1
   4. size 超过了 capacity，将尾节点删除，再插入一个新的节点 (key 和 val) 到头节点去
3. get(key) 先根据 key 去查找是否存在 key 的节点，如果存在就删除并返回，然后插入到头节点去；如果不存在，返回 -1
4. get 和 put 都是 O(n) 的时间复杂度，最差的情况需要遍历整个链表

public class LRUCache {
    // 用链表存储
    private final ListNode dummyNode;
    private final int capacity;
    private int size;
    public LRUCache(int capacity) {
        dummyNode = new ListNode(0);
        this.capacity = capacity;
    }
    public int getSize() {
        return size;
    }
    public int get(int key) {
        ListNode oldNode = deleteNode(key);
        if (oldNode != null) {
            insertHeadNode(oldNode);
            return oldNode.val;
        }
        return -1;
    }
    public void put(int key, int value) {
        // 先看是否存在key
        ListNode oldNode = deleteNode(key);
        if (oldNode != null) { // 存在key，直接替换
            oldNode.val = value;
            insertHeadNode(oldNode);
            return;
        }
        if (size < capacity) { // 容量未满，放在最前面
            // 容量未满&key不存在，插入新的到头节点
            ListNode newNode = new ListNode(value);
            newNode.key = key;
            insertHeadNode(newNode);
            size++;
        } else { // 容量已满
            // 丢弃最久未使用的（最后一个），将元素插入到最前面
            // 找到最后一个节点前一个节点
            ListNode lastPreNode = getLastPreNode();
            ListNode last = lastPreNode.next;
            lastPreNode.next = null;
            last.next = null;
            // 新建一个节点插入到头节点
            ListNode newNode = new ListNode(value);
            newNode.key = key;
            insertHeadNode(newNode);
        }
    }
    private ListNode getLastPreNode() {
        ListNode cur = dummyNode;
        ListNode pre = null;
        while (cur.next != null) {
            pre = cur;
            cur = cur.next;
        }
        return pre;
    }
    /**
     * 插入节点到头节点
     */
    private void insertHeadNode(ListNode n) {
        ListNode next = dummyNode.next;
        dummyNode.next = n;
        n.next = next;
    }
    /**
     * 删除某个key对应的ListNode并返回就ListNode
     */
    private ListNode deleteNode(int key) {
        ListNode pre = dummyNode;
        ListNode cur = dummyNode.next;
        while (cur != null) {
            if (cur.key == key) {
                // 删除cur
                pre.next = cur.next;
                cur.next = null;
                return cur;
            }
            pre = cur;
            cur = cur.next;
        }
        return null;
    }
}

public class ListNode {

    public int val;
    public int key;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

不足

1. get 和 put 的时间复杂度都是 O(N)
2. 根据 key 找到某个节点时每次都需要遍历整个链表来找到目标节点，时间复杂度为 O(1)
3. 删除某个节点也是需要遍历整个链表的，时间复杂度也是 O(1)

哈希表 + 双向链表 (推荐)

算法就像搭乐高：带你手撸 LRU 算法
LRU 算法设计

1. LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体

哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。

2. 双向链表的目的是删除节点时需要找到该节点的前驱节点，否则就需要遍历链表得到前驱节点，不能保证 O(1) 时间复杂度
3. 哈希表用来根据 key 定位节点，保证在 O(1) 的时间复杂度找到某个 key 对应的节点

代码实现

public class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}
public class DoubleList {
    // 头、尾节点
    private Node head;
    private Node tail;
    // 大小
    private int size;
    public DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.prev = null;
        head.next = tail;
        tail.prev = head;
        tail.next = null;
        size = 0;
    }
    // 在链表尾部添加节点 x，时间 O(1)
    public void addLast(Node x) {
        // node→tail→null
        // node→x→tail→null
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }
    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        x.prev = null;
        x.next = null;
        size--;
    }
    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public Node removeFirst() {
        if (head.next == tail) { // 当前没有节点
            return null;
        }
        Node n = head.next;
        remove(n);
//        Node n = head.next;
//        head.next = n.next;
//        n.next.prev = head;
//        n.next = null;
//        n.prev = null;
        return n;
    }
    // 返回链表长度，时间 O(1)
    public int size() {
        return size;
    }
}
public class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将该数据提升为最近使用的
        makeRecently(key);
        return map.get(key).val;
    }
    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // 删除旧的数据
            deleteKey(key);
            // 新插入的数据为最近使用的数据
            addRecently(key, val);
            return;
        }
        if (cap == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(key, val);
    }
    //* 将某个 key 提升为最近使用的 */
    private void makeRecently(int key) {
        Node x = map.get(key);
        // 先从链表中删除这个节点
        cache.remove(x);
        // 重新插到队尾
        cache.addLast(x);
    }
    /* 添加最近使用的元素 */
    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // 链表尾部就是最近使用的元素
        cache.addLast(x);
        // 别忘了在 map 中添加 key 的映射
        map.put(key, x);
    }
    /* 删除某一个 key */
    private void deleteKey(int key) {
        Node x = map.get(key);
        // 从链表中删除
        cache.remove(x);
        // 从 map 中删除
        map.remove(key);
    }
    /* 删除最久未使用的元素 */
    private void removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        Node deletedNode = cache.removeFirst();
        // 同时别忘了从 map 中删除它的 key
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }
}

• 时间复杂度：get 和 put 的时间复杂度都是 O(1)

LinkedHashMap 解法

用 Java 的内置类型 LinkedHashMap 来实现 LRU 算法

思路

1. 一个 LinkedHashMap 变量 cache(头部最近最少使用，尾部最近使用)，一个 capacity 最大容量 capacity
2. get(key) 方法
   1. 判断 cache 是否存在 key，如果不存在返回 -1
   2. 如果 cache 中存在，将改 key 对应的节点更新为最近使用 (先删除，再将节点添加到尾部)
3. put(key, val) 方法
   1. 判断 cache 中是否存在 key，如果存在，就更新 val，更新为最近使用
   2. 如果 cache 中不存在，再判断是否小于 capacity，是就添加到尾部；如果不小于 capacity，那么需要将头节点删除，再将该节点添加到尾节点去

代码

public class LRUCache {
    private LinkedHashMap<Integer, Integer> cache;
    private int capacity;
    public LRUCache(int capacity) {
        this.cache = new LinkedHashMap<>();
        this.capacity = capacity;
    }
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        if (cache.size() >= this.capacity) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    // 将key标记为最近使用
    private void makeRecently(int key) {
        Integer val = cache.get(key);
        if (val == null) {
            return;
        }
        cache.remove(key);
        cache.put(key, val);
    }
}